package 单周赛.history;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 *
 */
public class 第333场单周赛 {

    public static void main(String[] args) {

        mergeArrays(new int[][]{{1, 2}, {2, 3}, {4, 5}
        }, new int[][]{{1, 4}, {3, 2}, {4, 1}});


        minOperations(8433);

    }

    public static int[][] mergeArrays(int[][] nums1, int[][] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] ints : nums1) {
            map.put(ints[0], ints[1]);
        }
        for (int[] ints : nums2) {
            int key = ints[0];
            map.put(key, map.getOrDefault(key, 0) + ints[1]);
        }


        int[][] ans = new int[map.size()][2];
        int idx = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            ans[idx] = new int[]{entry.getKey(), entry.getValue()};
            idx++;
        }
        Arrays.sort(ans, (a, b) -> a[0] - b[0]);
        return ans;
    }

    public static int minOperations(int n) {
        int cnt = 0;

        while (n > 0) {
            cnt++;
            int i = find(n);

            int r = (int) Math.pow(2, i) - n;
            int l = n - (int) Math.pow(2, i - 1);
            n = Math.min(l, r);
        }
        return cnt;
    }

    private static int find(int n) {
        int ans = 13;
        int left = 0, right = 16;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (Math.pow(2, mid) > n) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    //：
    //[26,6,4,27,6,18]
    //输出：
    //6
    //预期：
    //3
    public int squareFreeSubsets(int[] nums) {
        int[] record = new int[31];
        for (int num : nums) {
            if (num != 4 && num != 9 && num != 16 && num != 25 &&
                    num != 8 && num != 12 && num != 20 && num != 24 && num != 28 &&
                    num != 18 && num != 27) {
                record[num]++;
            }
        }
        int n = 0;
        int mul = 0;
        for (int cnt : record) {
            if (cnt > 0) {
                n++;
                mul += cnt - 1;
            }
        }
        int ans = 1;
        for (int i = 0; i < n; i++) {
            ans *= 2;
            ans %= 1000000007;
        }
        ans--;
        int temp = ans;
        for (int i = 0; i < mul; i++) {
            ans += temp;
            ans %= 1000000007;
        }
        return ans;
    }

}
